import java.util.Arrays;

public class Binarysort {
    public static void main(String[] args) {
         int[] arr={10,11,7,6,8,9,12,1,4,2,3,5};
        BinaryTree binaryTree = new BinaryTree();
        for (int i = 0; i < arr.length; i++) {
               binaryTree.add(new Node(arr[i]));
        }
        binaryTree.Midorder();
        binaryTree.delnode(6);
        System.out.println();
        binaryTree.Midorder();

    }
}

class BinaryTree{
    private Node root;
    public void add(Node node) {//增加结点
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }
    public void Midorder(){//中序遍历
        if (root != null) {
            root.Midorder();
        } else {
            System.out.println("null");
        }
    }
    public Node search(int value){//找到要删除的目标节点
        if (root==null){
            return null;
        }
        return root.search(value);
    }
    public Node searchparent(int value){//找到要删除结点的父节点
        if (root==null){
            return null;
        }
        return root.searchparent(value);
    }
    public int delMin(Node node){//找到最小结点
        if (node.left!=null){
            node=node.left;
        }
        return node.value;
    }
    public void delnode(int value){
        if (root==null){
            return;
        }else {
            Node Targetnode = search(value);
            if (Targetnode==null){
                return;
            }
            if (root.left == null && root.right == null) {
                root = null;
                return;
            }
            Node Targetparentnode=searchparent(value);//要删除结点的父节点
            //删除叶子结点
            if (Targetnode.left==null&&Targetnode.right==null){
                if (Targetparentnode.left!=null&&Targetparentnode.left.value==value){
                    Targetparentnode.left=null;
                } else if (Targetparentnode.right!=null&&Targetparentnode.right.value==value) {
                    Targetparentnode.right=null;
                }
            } else if (Targetnode.left!=null&&Targetnode.right!=null) {//删除有两颗子树的结点
                    int Min=delMin(Targetnode.left);
                    Targetnode.value=Min;
            }else {
                if (Targetnode.left!=null){//删除只有一颗子树的子节点
                    if (Targetparentnode!=null){
                    if (Targetparentnode.left.value==value){//Targetnode是Targetparentnode的左子节点
                        Targetparentnode.left=Targetnode.left;
                    }else {
                        Targetparentnode.right=Targetnode.left;
                    }
                    }else {
                        root=Targetnode.left;
                    }
                }else {
                    if (Targetparentnode!=null){
                    if (Targetparentnode.left.value==value){//Targetnode是Targetparentnode的右子节点
                        Targetparentnode.left=Targetnode.right;
                    }else {
                        Targetparentnode.right=Targetnode.right;
                    }
                }else {
                        root=Targetnode.right;
                    }
                }
            }
        }
    }
}
class Node{
    public int value;
    public Node left;
    public Node right;

    public Node(int value) {
        super();
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    public void add(Node node) {//增加结点
        if (this.value > node.value) {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        }
        if (this.value < node.value) {
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }
    }

    public void Midorder(){//中序遍历
        if (this.left!=null){
            this.left.Midorder();
        }
        System.out.println(this);
        if (this.right!=null){
            this.right.Midorder();
        }
    }


    public Node search(int value){//找到该节点
        if (this.value==value){
            return this;
        }
        if (value<this.value){
            if (this.left==null){
                return null;
            }
                return this.left.search(value);
        } else {
                if (this.right==null){
                    return null;
                }else {
                    return this.right.search(value);
                }
            }
    }
    public Node searchparent(int value){//找到父节点
        if ((this.left!=null&&this.left.value==value)||(this.right!=null&&this.right.value==value)){
            return this;
        }else {
        if (this.value>value&&this.left!=null){
            return this.left.searchparent(value);
        }else if (this.value<=value&&this.right!=null){
            return this.right.searchparent(value);
        }else {
        return null;
        }
    }
    }




}
